This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. ""119 from an application entitled CLIPPING PROCESSING METHOD earlier filed in the Korean Industrial Property Office on Apr. 29, 1998, and there duly assigned Serial No. 98-15353.
1. Field of the Invention
The present invention relates to a graphics processing method, and more particularly, to a clipping processing method.
2. Description of the Related Art
A three-dimensional (3D) graphics technique is widely used in various apparatuses communicating with the user through a screen, for example, in multimedia devices, game machines, and personal computers. Its application range is also gradually widening. The 3D graphics processing can be divided into geometry processing and rasterization. The geometry processing includes transformation, lighting, clipping and perspective projection. The rasterization includes interpolation and texture mapping.
As one example of a 3D graphics processing device, there is illustrated a 3D simulator device in FIG. 1. The 3D simulator device includes a control section 100, a virtual 3D space calculation section 102, an image synthesis section 104, and a cathode ray tube (CRT) 106. The 3D simulator device of FIG. 1 is disclosed in detail in U.S. Pat. No. 5,559,937, issued on Sep. 24, 1996. The 3D simulator device of FIG. 1 will now be described with reference to the above U.S. Pat. No. 5,559,937 on the assumption that it is applied to a 3D game. The virtual 3D space calculation section 102 sets a virtual 3D space in response to control signals from the control section 100 and to a game program stored in a central processing unit mounted in the control section 100. That is, the virtual 3D space calculation section 102 calculates the position of a 3D object and the arranged direction thereof. The image synthesis section 104 synthesizes a pseudo-3D image in response to setting information on the virtual 3D space from the virtual 3D space calculation section 102. The pseudo-3D image synthesized from the image synthesis section 104 is transmitted to the CRT 106 and displayed on a CRT screen. Then an observer who is a game player can see a 3D image appearing on the virtual 3D space through the pseudo-3D image displayed on the CRT screen.
The virtual 3D space where the observer sees the 3D image corresponds to a 3D image display region. This display region is represented as a viewing frustum 200 consisting of 6 planes 202-212, as indicated in FIG. 2. An observer 210 sees the 3D image within the viewing frustum 200 through the screen of the CRT 106. In this case, only an object within the viewing frustum 200 appears on the screen.
Meanwhile, the 3D image displayed within the viewing frustum 200 should be changed by rotation or conversion processing according to a change in factors, for example, the viewpoint position or line-of-sight direction of the observe 210, or the position or moving direction of a vehicle in which the observer 210 is seated. xe2x80x9cClipping processingxe2x80x9d is one of 3D graphics processing for this and it is processed by the image synthesis section 104.
In clipping processing of graphics processing, it is simple to process objects which are inside or outside the viewing frustum 200, but it is necessary to perform interpolation with respect to objects which are on the boundary of the viewing frustum 200. That is, images which are outside the viewing frustum 200 whose vertex is the position of observer""s eyes are excluded from an object to be processed, images which are inside the viewing frustum 200 are included for rendering, and the other part except a part within the viewing frustum 200 among images which are on the boundary of the viewing frustum 200 is clipped. The images for clipping processing are divided into polygons which are geometric units for graphics rendering.
In the following description, a triangle will be proposed as one form of the polygons. The triangle to be clipped in geometric units for graphics rendering is defined by three vertices each further defined in terms of the x, y, z coordinates, the R, G, B, A color values, and the U, V, S, T parameter values. This triangle is clipped with respect to each of the 6 planes 202-212 constituting the viewing frustum 200. Therefore, the 6 planes 202-212 correspond to xe2x80x9cclipping planesxe2x80x9d.
FIG. 3 is an exemplary diagram illustrating triangles which are situated differently from each other with respect to one clipping plane. In FIG. 3, the clipping plane 206 is an example of one plane constituting the viewing frustum 200, and three triangles T1-T3 show the cases that triangles to be clipped can be situated with respect to the clipping plane 206. For the clipping processing, it should be determined whether a triangle is outside the viewing frustum 200 with respect to the clipping plane 206 like the triangle T1, whether it is inside the viewing frustum 200 like the triangle T3, or whether it is on the boundary of the clipping plane 206 like the triangle T2. The triangle T2 should be clipped, T1 is excluded from an object to be processed, and T3 is included as an object for rendering. If the triangle T2 is clipped, a quadrangle is left. This quadrangle is cut into two triangles.
FIG. 4 illustrates a general clipping processing procedure executed by, for example, the image synthesis section 104 of the 3D simulator device of FIG. 1. A triangle to be clipped is inputted at step 300. The first to sixth clipping planes 202-212 constituting the viewing frustum 200 are sequentially clipped at steps 302-312.
The clipping processing commonly performed at steps 302-312 shown in FIG. 4 is illustrated in FIG. 5. For the clipping processing, the position of a triangle to be clipped with respect to a clipping plane is determined. Thereafter, the triangle may be excluded from an object to be processed, included for rendering, or clipped according to the determined result.
A plane equation defining one infinite plane is represented by the following equation (1):
f(x,y,z)=ax+by+cz+dxe2x80x83xe2x80x83(1)
where a, b, c and d are coefficients.
If a functional value f(x,y,z) at a point (x,y,z) is a positive value, that point is inside the plane, if it is a negative value, that point is outside the plane, and if it is 0, that point is on the plane. Therefore, the functional value for each vertex of the inputted triangle is calculated by the equation (1) to determine where the triangle is positioned.
At step 400, the functional values for three vertices of the triangle are calculated by the equation (1) with respect to the clipping plane. Assuming that three vertices are V1, V2 and V3, functional values f1, f2 and f3 at the vertices V1, V2 and V3 are calculated by substituting coordinate values of the vertices V1, V2 and V3 for the equation (1). At steps 402 and 404, the position of the triangle is determined. That is, whether the functional values f1 (=f(V1)), f2 (=f(V2)) and f3 (=f(V3)) are all less than 0 is checked at step 402. If they are less than 0, it is determined that the triangle is outside the clipping plane 206 like the triangle T1 shown in FIG. 3. In such a case, the triangle is excluded from an object to be processed and step 402 is followed by step 300 illustrated in FIG. 4. If all the functional values f1, f2 and f3 are not less than 0, it is checked at step 404 whether they are all greater than 0. If they are all greater than 0, it is determined that the triangle is inside the clipping plane 206 like the triangle T3 shown in FIG. 3. In that case, step 404 is followed by corresponding one among steps 302-312 to perform the clipping processing with respect to the next clipping plane. If the clipping processing with respect to the sixth clipping plane has been done, step 314 is performed. If all the functional values f1, f2 and f3 are not greater than 0 at step 404, it is judged that the triangle is on the boundary of the clipping plane 206 like T2 illustrated in FIG. 3. Then intersecting points are calculated and new vertices are made at step 406. Step 406 is followed by a corresponding one among steps 302-312 or by step 314 if the clipping processing with respect to the sixth clipping plane has been performed.
Through steps 302-312 shown in FIG. 4, the six clipping planes are sequentially clipped. Thereafter, if there is the remaining quadrangle, it is divided into two triangles at step 314 and a series of steps beginning from step 300 are performed. If not, rendering processing is executed at step 316 and step 316 is followed by step 300.
In the above-described clipping processing, the functional values of a plane equation for three vertices of a triangle should be calculated to determine where the triangle is situated. However, a multiplication operation and an addition operation are needed 3 times per operation to calculate the functional value using the plane equation (1). Moreover, Boolean operation is implemented at steps 402 and 404 shown in FIG. 5 twice per step. That is, in order to judge the position of one triangle, the multiplication operation is needed 9 times, the addition operation 9 times, the comparison operation 6 times, and the Boolean operation 4 times. Since these operations should be calculated with respect to 6 planes constituting the viewing frustum, lots of calculations are demanded.
Generally, the geometric processing among the 3D graphics processing requires a floating point calculation occupied mainly by the clipping processing. The number of operations necessary for the clipping processing has a great influence on the performance of graphics. Therefore, the clipping processing is a main obstacle to the improvement of the performance of graphics.
It is therefore an object of the present invention to provide a clipping processing method which can simplify a clipping process in graphics processing.
It is another object of the present invention to provide a clipping processing method which can reduce the number of operations for clipping processing in graphics processing.
To achieve these objects, there is provided a method for determining a position at which a polygon to be clipped is situated with respect to a clipping plane to perform clipping processing. The method includes the steps of selecting a bounding volume sufficiently enclosing the polygon, and judging a position at which the bounding volume is situated with respect to the clipping plane to be the position at which the polygon is situated.